package 力扣91;

/**
 * @ClassName : Day7_61_旋转链表
 * @Author : 骆发茂
 * @Date: 2021/12/18 13:03
 * @Description : https://leetcode-cn.com/problems/rotate-list/
 * https://leetcode-cn.com/problems/rotate-list/solution/kuai-man-zhi-zhen-xi-jie-yao-gao-hao-by-lilychao/
 * 解题思路
 * 因为k有可能大于链表长度，所以首先获取一下链表长度len。如果k % len == 0，等于不用旋转，直接返回头结点。否则：
 * <p>
 * 快指针先走k步。
 * 慢指针和快指针一起走。
 * 快指针走到链表尾部时，慢指针刚好走到旋转链表（返回的链表）的尾部。把快指针指向的节点连到原链表头部，慢指针指向的节点断开和下一节点的联系。
 * 返回结束时慢指针指向节点的下一节点。
 * <p>
 * 作者：programmerY
 * 链接：https://leetcode-cn.com/problems/rotate-list/solution/java-shuang-zhi-zhen-100-by-programmery-31h5/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
public class Day7_61_旋转链表 {
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode rotateRight(ListNode head, int k) {
            if (head == null || head.next == null || k == 0) {
                return head;
            }
            ListNode tmp = head;
            int count = 0;
            while (tmp != null) {
                tmp = tmp.next;
                count += 1;
            }
            k = k % count;
            if (k == 0) return head;
            ListNode p = head, fast = head, slow = head;
            //让fast先走k步，刚好就是到了新的链表的头指针位置
            //fast当前位置就是head要放的位置
            //fast当前位置就是head要放的位置
            //fast当前位置就是head要放的位置
            for (int i = 0; i < k; i++) {
                fast = fast.next;
            }
            // 使用「快慢指针」找到倒数第 k 个节点（新头结点）：slow 会停在
            // 「新头结点」的「前一位」，也就是「新尾结点」
            //每次走一步，
            //对于fast和slow的作用，通俗的理解是fast用来定位head所要去的位置，定位好位置后，利用while，将fast往后移。
            //fast每往后移动一步，slow也跟着移动一步。因为fast当前位置就是head要放的位置，fast后面还有多少，也意味着head后面有多少。
            //移动完成后，从head到slow这一段，就是将要放在末尾的部分，而从slow.next位置开始往后都是要放在前面的部分。
            //即slow.next变成头部,赋给新的nHead指针，指向slow.next到fast这一段。在新头部指针弄好后。
            //因为head到slow这一段放在末尾，slow.next就要置为null，成为尾部。而fast.next紧跟着head,即head到slow这一段的头部head指针
            while (fast.next != null) {
                fast = fast.next;
                slow = slow.next;
            }
            ListNode newHead = slow.next;
            slow.next = null;
            fast.next = head;
            return newHead;
        }
    }

}